传送门在这:我是传送门QwQ
其实不难发现,我们需要算的就是 ∑ai (其中 ai 为点 i 的通电概率) 。我们需要算出每个点的通电概率即可。因为有些点可以自己发电,所以我们要分别考虑父亲和儿子的通电情况。
因为直接设通电概率有些棘手,我们设 fi 表示点 i 的儿子没有向点 i 通电的概率,这个比较好算,我们顺带算上点 i 自己发电的概率。
枚举每一个儿子,对于这个儿子只有两种情况:该儿子没有通上电,该儿子通上电了且传送失败。两种情况的概率都很好算。我们可以列出转移方程:
fu=(1−qu)⋅∏(fv+(1−fv)⋅(1−Gi.p))其中 (1−qu) 显然为该点本身不通电的概率,然后枚举儿子 v ,fv 就是该儿子本来就没有通上电的概率,(1−fv)⋅(1−Gi.p) 就是通上电的传送失败(注:Gi.p 是当前连接 u,v 的边的通电概率) 。
那么如何计算父亲传来的电呢?设 gi 表示点 i 的父亲没有向点 i 通电的概率。计算一下父节点不通电的概率,注意不要计算上该儿子的贡献,不然会乱。计算完不通电的概率后分上面两种情况讨论即可。
res=gu⋅fv/(fv+(1−fv)⋅(1−Gi.p))gv=res+(1−res)⋅(1−Gi.p)两边 dfs 就可以搞定。
Code:
1 |
|
本文标题:【题解】 [SHOI2014]概率充电器 概率DP loj2192
文章作者:Qiuly
发布时间:2019年05月02日 - 00:00
最后更新:2019年05月05日 - 10:07
原始链接:http://qiulyblog.github.io/2019/05/02/[题解]loj2192/
许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。
v1.5.2